package tests;

import java.util.Random;

import linkcut.AuxVertex;
import linkcut.LinkCutTree;

import org.junit.Assert;
import org.junit.Test;


public class StressTest {
	
	@Test
	public void test() {
		int n = 200000;
		AuxVertex<Integer>[] vertices = new AuxVertex[n];
		LinkCutTree<Integer> tree = new LinkCutTree<Integer>();
		Random rand = new Random();
		
		for (int i = 0; i < n; i++) {
			vertices[i] = tree.makeTree(i);
		}
		
		for (int i = 0; i < 3 * n / 4; i++) {
			AuxVertex<Integer> v1;
			AuxVertex<Integer> v2;
			do {
				v1 = vertices[rand.nextInt(n)];
				v2 = vertices[rand.nextInt(n)];
			} while (v1 == v2 || (tree.findRoot(v1) == tree.findRoot(v2)) || !tree.isRepresentedRoot(v1));
			
			tree.link(v1, v2);
			Assert.assertTrue(tree.findRoot(v1) == tree.findRoot(v2));
		}

		for (int i = 0; i < n / 2; i++) {
			int k;
			do {
				k = rand.nextInt(n);
			} while (tree.isRepresentedRoot(vertices[k]));	
			AuxVertex<Integer> oldRoot = tree.findRoot(vertices[k]);
			tree.cut(vertices[k]);
			Assert.assertNotEquals(oldRoot, tree.findRoot(vertices[k]));
		}
	}
}
